This relates to data processing apparatus for encoding and decoding two-dimensional information in an efficient manner. More particularly, this relates to apparatus for the creation of a two-dimensional cosine transform and its inverse.
Image data compression has been a topic of considerable interest in recent years because of the burgeoning fields of information and communication. Compression of image data is necessary because in order to achieve pleasing results a picture must contain a large number of pixels, or elemental picture elements. Such images, however, contain a large amount of redundant information. Researchers have tried to encode images in a number of ways to reduce this redundancy and to thereby realize transmission and storage savings. These encoding approaches can be broadly divided into pulse code modulation, interpolative or extrapolative coding, vector quantization, and transform coding.
In predictive coding, such as in the differential pulse code modulation (DPCM) approach, an attempt is made to predict the pixel to be encoded. The prediction is made by using the encoded values of the previously encoded pixels. Generally, these pixels are combined to generate a predicted value. The difference between the actual value and the generated predicted value is quantized and encoded prior to transmission or storage. Adaptive DPCM, where the prediction algorithm is based on local picture statistics, is a variation on this approach.
In interpolative and extrapolative coding, only a subset of the pixels is sent to the receiver. The receiver must then interpolate the available information to develop the decoded pixels.
In vector quantization, an image block is decomposed into a set of vectors. From the possible signal patterns and corresponding vectors, a subset of representative vectors is selected and included in a code book. When encoding, the developed sets of vectors are replaced with the closest representative vectors in the code book, and compression is achieved by further replacing the representative vectors with labels.
Finally, in transform coding, instead of coding the image as discrete intensity values of sampling points, an alternative representation is made first by transforming blocks of pixels into a set of coefficients. It is the coefficients that are quantized and transmitted. Several transformations have been used in the art, such as the Hadamard, the Karhunen-Loeve, and the Discrete Cosine Transforms. These transforms conserve the signal energy in the transform domain but, typically, most of the energy is concentrated in relatively few samples. Samples that are very close to zero need not be transmitted, and samples of relatively low value can be quantized coarsely. This results in substantial compression of the data that needs to be either stored or transmitted. Huffman coding is often used after quantizing to further reduce the transmission rate.
The Discrete Cosine Transform is a commonly applied transform. It is usually realized with processors built from TTL or ECL hardware which processes video at rates of about 8-10 megasamples per second. The transformation consists of multiplying an n.times.n matrix by an n element vector. Since parallel hardware multipliers are expensive, most theoretical work has concentrated on exploiting the symmetries of the cosine matrix to partition it into smaller matrices, so that the total number of multiplications is reduced. This results a variety of "Fast Discrete Cosine Transform" algorithms, which are close cousins of the FFT.
One such algorithm for computing the Discrete Cosine Transform is described by C. H. Smith in a paper entitled "A Fast Computational Algorithm for the Discrete Cosine Transform," published in the IEEE Transactions on Communication, September 1977. Based on this algorithm, Widergren et al., in U.S. Pat. No. 4,385,363, issued May 24, 1983, describe apparatus for developing the Discrete Cosine Transform by the use of a plurality of shuffle and add, together with shuffle, multiply and add circuits which employ discrete arithmetic logic units.
Employing a different architecture, R. L. Wilhelm describes a multiple point discrete transform processor in U.S. Pat. No. 4,449,194, issued May 15, 1984. The Wilhelm processor approximates each term of the Discrete Cosine Transform by power of 2 terms so that all mathematical steps are performed by shifting and/or subtracting digital signals.
Moving from TTL and ECL standard chips to VLSI designs allows more flexibility in multiplier designs. It is an object of this invention, therefore, to develop a Discrete Cosine Transform architecture that accomplishes the transformation more efficiently by utilizing the advantages inherent in VLSI designs.